class Solution {
public:
    vector<int> findPosition(const vector<int> numbers, int total, const vector<int> &count) {
      vector<int> curCount(total);
      int n = numbers.size();
      int sum = 0;
      vector<int> ret;

      for (int i = 0, j = 0; i < n; ++i) {
        if (numbers[i] < 0) {
          while (j <= i) {
            if (numbers[j] >= 0) {
              if (--curCount[numbers[j]] < count[numbers[j]]) {
                --sum;
              }
            }
            ++j;
          }
        } else {
          ++curCount[numbers[i]];
          if (curCount[numbers[i]] <= count[numbers[i]]) {
            ++sum;
          }
          while (i - j + 1 > total) {
            if (numbers[j] >= 0) {
              if (--curCount[numbers[j]] < count[numbers[j]]) {
                --sum;
              }
            }
            ++j;
          }
          if (sum == total) {
            ret.push_back(j);
          }
        }
      }
      return ret;
    }

    vector<int> findSubstring(string S, vector<string> &L) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
      int len = L[0].length();
      map<string, int> hash;
      vector<int> count(L.size());
      vector<int> ans;

      for (int i = 0; i < L.size(); ++i) {
        if (!hash.count(L[i])) {
          hash[L[i]] = i;
        }
        ++count[hash[L[i]]];
      }
      for (int i = 0, j =0; i < len; ++i) {
        vector<int> numbers;
        for (j = i; j + len <= S.length(); j += len) {
          string substring = S.substr(j, len);
          if (hash.count(substring)) {
            numbers.push_back(hash[substring]);
          } else {
            numbers.push_back(-1);
          }
        }
        vector<int> ret =  findPosition(numbers, L.size(), count);
        for (int k = 0; k < ret.size(); ++k) {
          ans.push_back(i + ret[k] * len);
        }
      }
      return ans;

    }
};
